The present invention relates to the field of automatic development of complex structures; more particularly, the present invention relates to the automatic creation of the topology, component sizing, placement, and routing of components in complex structures, such as, for example, electrical circuits or mechanical system.
Engineers are often called upon to design complex structures, such as electrical circuits or mechanical systems, that satisfy certain high-level design goals or requirements. The design of such structures is ordinarily thought to require human intelligence and typically involves intricate tradeoffs between competing design considerations.
Electrical circuits, for example, are composed of a variety of types of components, including resistors, capacitors, inductors, diodes, transistors, and energy sources. The individual components of an electrical circuit may be connected to one another in a particular topological arrangement to form an electrical circuit. Moreover, the actual physical location on a printed circuit board, a silicon wafer, or other substrate is often important in determining the behavior or usefulness of a circuit.
Similarly, mechanical structures are composed from a variety of types of components, including springs, dash pots, wheels, belts, gears, pulleys, and so forth. The individual components of a mechanical system are connected to one another in a particular topological arrangement. Moreover, the actual physical location of the components, in two or three dimensions, in relation to each other plays a crucial role in determining the behavior of a mechanical system.
In designing an electrical circuit, mechanical structure, or other complex structure, the goal is to attain certain desired values of one or more observable behavioral quantities (e.g., certain voltages at certain times or frequencies at a certain probe point in the circuit, velocity of a certain mechanical part at a certain time) and, often, certain values of certain additional characteristics (e.g., the cost or number of components).
The creation of a complex structure typically requires creation of the topology, component sizing, placement, and routing of components of complex structures where the structure satisfies certain user-specified high-level design requirements.
The topology of an electrical circuit or mechanical system refers to the number of components, the type of each component (e.g., resistor, spring), and a list of all the connections between the leads of the components (e.g., leads of a resistor, ends of a spring). Topology also includes information about whether a particular lead or other type of interface point of a particular component is connected, in a graphical sense, to the lead of another component. That is, xe2x80x9ctopologyxe2x80x9d herein refers to whether or not a connection exists between two particular leads or interface points of components, and does not include information about the actual physical location (placement) of the component or about the actual physical location (routing) of the connecting means (wires, in the case of circuits) that connect the leads of components.
The sizing of a circuit refers to the component value(s) of each component. The sizing of a component is typically a numerical value (e.g., the capacitance of a capacitor, the spring constant of a spring), but is sometimes a non-numerical parameter (e.g., whether an electrical energy source is AC or DC, or the material used for a particular mechanical component).
Placement involves the assignment of each of the circuit""s components to a particular physical location. In the case of electrical circuits, electrical components are placed onto a printed circuit board, silicon wafer, or other substrate. In mechanical systems, placement involves the assignment of each of the system""s components to a particular physical location in two or three dimensions.
Routing involves the assignment of a particular physical location to the connecting mechanism (e.g., wires) between the leads of the structure""s components.
The actual physical location (placement) of components, in two or three dimensions, is almost always crucial to the operation of mechanical systems.
Similarly, for electrical circuits, the actual physical location (placement) of components and the actual physical location (routing) of the wires that connect the components is often important for various different reasons. For example, it may be desirable to minimize the total area occupied by the circuit. Two circuits may have identical topology and sizing (e.g., the same number of transistors and capacitors whose leads are topologically connected in the same way), but one circuit may be preferable to the other because it is laid out in such a way that it occupies less space. In addition, the routing is often crucial because it affects the distance between two components (thereby affecting, say, the time required for an electrical signal to travel between two components along a wire). Also, the exact physical location of each component and wire is important because electrical components subtly interact with one another based on their physical location. These interactions, called parasitic effects, are generally small in magnitude (relative to other effects within the circuit) and can sometimes be ignored in simple circuits operating in non-challenging regimes. However, for many operating regimes, it is impossible to design a practical circuit without considering parasitic effects. For example, parasitic effects may crucially affect the performance of a circuit operating, say, at radio frequencies (RF).
Search Techniques
There are many techniques for searching a space for its optimum points, including, as examples, hill-climbing, simulated annealing, and genetic programming.
A search through any search space involves starting with one or more entities (points) from the search space, ascertaining the xe2x80x9cgoodnessxe2x80x9d of the entity for solving the problem at hand, creating a new candidate entity by modifying an existing entity, ascertaining the xe2x80x9cgoodnessxe2x80x9d of the new candidate entity, and using the xe2x80x9cgoodnessxe2x80x9d measure to select among entities. The xe2x80x9cgoodnessxe2x80x9d measure is typically called the xe2x80x9cfitness measurexe2x80x9d when talking about genetic programming and xe2x80x9cenergy levelxe2x80x9d when talking about simulated annealing. The term xe2x80x9cfitnessxe2x80x9d will be used below to refer to either the fitness measure in a genetic programming sense and the energy level in a simulated annealing sense.
Search by Use of Hill Climbing
Simple hill climbing involves starting with a single initial entity (point) in the search space, ascertaining the fitness of the entity, creating a new (usually nearby) candidate entity, ascertaining the fitness of the new candidate entity, and using the fitness measure to select between the preexisting entity and the new candidate entity. In hill climbing, a new candidate point with a better fitness than the preexisting point is unconditionally selected. Conducting a search using hill climbing through a space of entities in a nontrivial problem typically results in the search becoming trapped at a local optimum point rather than finding the global optimum point of the search space.
Search by Use of Simulated Annealing
Simulated annealing (Kirkpatrick, Gelatt, and Vecchi 1983; Aarts and Korst 1989) resembles hill climbing in that it is a point-to-point search technique. Like hill climbing, it employs a problem-specific probabilistic modification operation (usually called a mutation when talking about simulated annealing) for modifying the current entity (point) in the search space in order to obtain a new candidate entity. At each step of the search, the current point in the search space is modified using the modification operator and the new point""s fitness is ascertained. In general terms, the beginning of a run of simulated annealing conducts a broad-based search for promising regions of the search space, while the end of the run resembles does hill-climbing in a localized area.
Specifically, simulated annealing involves starting with a single initial entity (point) in the search space, ascertaining the fitness of the entity, creating a new candidate entity, ascertaining the fitness of the new candidate entity, and using the fitness measure to select between the preexisting entity and the new candidate entity. Simulated annealing always selects the new candidate entity if it is better than the preexisting entity. However, simulated annealing differs from hill climbing in the way it handles the case when the new candidate entity is worse than the preexisting entity. In this event, the Metropolis algorithm and the Boltzmann equation are applied to determine whether to accept a non-improving new candidate entity. A run of simulated annealing is governed by an annealing schedule in which a temperature T changes as the run proceeds (typically in an exponentially decreasing way). The effect of the Metropolis algorithm and the Boltzmann equation are that the probability of acceptance of a non-improving modification is greater if the fitness difference is small or if the temperature T is high. Thus, fairly large non-improving modifications are likely to be accepted early in the run (when the temperature is high), while only small non-improving modifications are likely to be accepted later in the run. In other words, simulated annealing becomes very similar to hill climbing in later stages of the run. If a modification is not accepted at any step of the run of simulated annealing, the probabilistic modification operator is reinvoked to produce another new point.
Simulated annealing is similar to genetic programming in that it sometimes accepts a newly created point that is known to be inferior in the hope that it will lead to better points. Simulated annealing differs from genetic programming in that simulated annealing always accepts an improving modification while genetic programming do not. Simulated annealing and hill climbing differ from searches conducted by the genetic programming (described below) in that there is no population of entities in simulated annealing or hill climbing. Only one entity (point) is retained at each generation of the search in simulated annealing or hill climbing. Because there is no population in simulated annealing or hill climbing, there is no analog to the crossover operation of genetic programming (where two parents recombine to produce offspring).
Search by Use of Genetic Programming
xe2x80x9cGenetic programmingxe2x80x9d (also referred to as the xe2x80x9cnon-linear genetic algorithmxe2x80x9d or the xe2x80x9chierarchical genetic algorithmxe2x80x9d in previous years) is described in the book entitled Genetic Programming: On the Programming of Computers by Means of Natural Selection, by John R. Koza, Cambridge, Ma.: The MIT Press, 1992; the book entitled Genetic Programming II: Automatic Discovery of Reusable Programs, by John R. Koza, Cambridge, Ma.: The MIT Press, 1994; Genetic Programming III: Darwinian Invention and Problem Solving by John R. Koza, Forrest H Bennett III, David Andre, and Martin A. Keane, San Francisco, Calif.; Morgan Kaufmann Publishers, 1999; and in U.S. Pat. Nos. 4,935,877, 5,136,686, 5,148,513, 5,343,554, 5,742,738, and 5,867,397.
Genetic programming is referred to as xe2x80x9cnon-linearxe2x80x9d or xe2x80x9chierarchicalxe2x80x9d because the original genetic algorithm described by John H. Holland in Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, Ann Arbor, Mich.: University of Michigan Press, Second edition, Cambridge, Ma.: The MIT Press, 1975, operated on linear strings of characters (resembling chromosomes in nature), whereas genetic programming operates on hierarchical program trees of various sizes and shapes.
Genetic programming is capable of evolving computer programs that solve, or approximately solve, a variety of problems from a variety of fields. Genetic programming may start with a xe2x80x9cprimordial oozexe2x80x9d of randomly generated programs composed of the available programmatic ingredients and then applies the principles of animal husbandry to breed a new (and often improved) population of programs. Genetic programming may perform the breeding in a domain-independent way using the Darwinian principle of survival of the fittest, an analog of the naturally-occurring genetic operation of crossover (sexual recombination), and occasional mutation. The crossover operation is designed to create syntactically valid offspring programs (given closure amongst the set of ingredients). Genetic programming combines the expressive high-level symbolic representations of computer programs with the near-optimal efficiency of learning associated with Holland""s genetic algorithm. A program that solves (or approximately solves) a given problem often emerges from this process.
As demonstrated in the book entitled Genetic Programming II: Automatic Discovery of Reusable Programs, by John R. Koza, Cambridge, Ma.: The MIT Press, 1994, genetic programming can evolve multi-part programs having a main program and one or more reusable, parameterized, hierarchically-called subprograms (called automatically defined functions or ADFs). See U.S. Pat. No. 5,343,554, entitled xe2x80x9cA Non-Linear Genetic Process for Data Encoding and for Solving Problems Using Automatically Defined Functionsxe2x80x9d, issued Aug. 30, 1994, by Koza, John R., and Rice, James P.
Architecture-altering operations, such as described in Genetic Programming III: Darwinian Invention and Problem Solving (1999), enable genetic programming to automatically determine the number of subroutines, the number of arguments that each possesses, and the nature of the hierarchical references, if any, among such automatically defined functions. Certain architecture-altering operations also enable genetic programming to automatically determine whether and how to use internal memory, iterations, and recursion in evolved programs. See U.S. Pat. No. 5,742,738, entitled xe2x80x9cSimultaneous Evolution of the Architecture of a Multi-part Program to Solve a Problem Using Architecture Altering Operations,xe2x80x9d issued Apr. 21, 1998, by Koza, John R., Andre, David, and Tackett, Walter Alden.
Genetic programming may breed computer programs to solve problems by executing the following steps:
(1) Generate an initial population of random compositions of the functions and terminals of the problem (i.e., programs).
(2) Iteratively perform the following substeps (referred to herein as a generation) on the population until the termination criterion has been satisfied:
(A) Execute each program in the population and assign it a fitness value using the fitness measure.
(B) Create a new population of programs by applying the following operations. The operations are applied to program(s) selected from the population with a probability based on fitness (with reselection allowed).
(i) Reproduction: Copy the selected program to the new population.
(ii) Crossover: Create a new offspring program for the new population by recombining randomly chosen parts of two selected programs.
(iii) Mutation: Create one new offspring program for the new population by randomly mutating a randomly chosen part of the selected program.
(iv) Architecture-altering operations: Select an architecture-altering operation from the available repertoire of such operations and create one new offspring program for the new population by applying the selected architecture-altering operation to the selected program.
(3) Designate the individual program that is identified by result designation (e.g., the best-so-far individual) as the result of the run of genetic programming. This result may be a solution (or an approximate solution) to the problem.
Genetic programming conducts a search for a solution, or approximate solution, to a problem. It is preferable to hill climbing because hill-climbing operates on only a single entity (point) in the search space of the problem and because hill-climbing greedily unconditionally selects a better point in preference to a worse point. Because of this, hill climbing tends to become trapped on local optimum points that are not global optimum points. Simulated annealing also operates on a single entity (point) in the search space of the problem; however, simulated annealing is preferable to hill climbing because it typically uses the Metropolis algorithm and the Boltzmann equation to attempt to avoid becoming entrapped on locally optimum points.
Genetic programming is preferable to simulated annealing (which resembles a genetic algorithm operating on a population of size 1) because the existence of a population permits crossover (recombination) to occur between two (or more) parents, each chosen probabilistically based on their fitness. Experience indicates that the recombination of parts of already fit parents often yields superior offspring in a far more rapid way than that provided by search techniques that lack recombination.
Until recently, there has been no general technique for automatically creating the topology and sizing for an analog electrical circuit from a high-level statement of the circuit""s desired behavior. However, see U.S. Pat. No. 5,867,397, entitled xe2x80x9cMethod and Apparatus for Automated Design of Complex Structures Using Genetic Programming,xe2x80x9d issued Feb. 2, 1999.
There has been extensive previous work on the problem of automating various aspects of the design of electrical circuits and other structures usmg simulated annealing, artificial intelligence, and other techniques, including genetic algorithms (Kruiskamp, Wim and Leenaerts, Domine, DARWIN: CMOS opamp synthesis by means of a genetic algorithm, Proceedings of the 32nd Design Automation Conference, New York, N.Y.: Association for Computing Machinery, 1995; Grimbleby, J. B., Automatic analogue network synthesis using genetic algorithms, Proceedings of the First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, London: Institution of Electrical Engineers, 1995; Thompson, Adrian, Silicon evolution, in Koza, John R., Goldberg, David E., Fogel, David B., and Riolo, Rick L. (editors), Genetic Programming 1996: Proceedings of the First Annual Conference, Cambridge, Ma.: MIT Press, 1996; Schnecke, V. and Vornberger, O. Genetic design of VLSI layouts. Proceedings of the First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications (GALESIA). London: Institution of Electrical Engineers. 1995). All of the existing techniques address only one or two of the four aspects (topology, sizing, placement, and routing) of circuit design. In addition, most of these techniques are limited to certain highly specialized types of circuits. Many of these techniques require the user to supply a reasonably good working circuit as a starting point (with the automated technique then merely adjusting the sizing of the components), while others involve choosing pre-established alternative subcircuits for preestablished places within a preestablished overall circuit design. Many of the techniques require repeated interactive intervention by the user. Generally, the decisions that are automated are only a small subset of the decisions that must be made.
Recently, a general technique using genetic programming has emerged for automatically creating the topology and sizing for an analog electrical circuit from a high-level statement of the circuit""s desired behavior (Koza, John R., Bennett III, Forrest H., Andre, David, Keane, Martin A., and Dunlap, Frank, Automated synthesis of analog electrical circuits by means of genetic programming, IEEE Transactions on Evolutionary Computation, 1(2),1997. See U.S. Pat. No. 5,867,397, entitled xe2x80x9cMethod and Apparatus For Automated Design of Complex Structures Using Genetic Programmingxe2x80x9d, issued Feb. 2, 1999).
The topology and sizing of numerous circuits have been automatically synthesized using genetic programming, including lowpass, highpass, bandpass, bandstop, crossover, multiple bandpass, and asymmetric bandpass filters, amplifiers, computational circuits, a temperature-sensing circuit, a voltage reference circuit, frequency-measuring circuits, and source identification circuits.
Genetic programming can be applied to circuit design by establishing a mapping between the rooted, point-labeled trees (i.e., acyclic graphs) with ordered branches used in genetic programming and the specialized type of line-labeled cyclic graphs germane to electrical circuits.
For electrical circuits, an embryo consisting of one (and sometime more) modifiable wires may be used as a starting point. The embryo may be embedded into a test fixture consisting of fixed (hard-wired) components (such as a source resistor and a load resistor) and certain fixed wires that provide connectivity to the circuit""s external inputs and outputs. Until the modifiable wires of the embryo are modified by the developmental process, the initial circuit (e.g., the embryo and test fixture) produces only trivial output. A non-trivial electrical circuit is developed by progressively applying the functions in a circuit-constructing program tree (in the population being bred by genetic programming) to the modifiable wires of the original embryo and, during the developmental process, to newly created modifiable components and modifiable wires of the developing circuit.
Each branch of the program tree may be created in accordance with a constrained syntactic structure. Branches may be composed of construction-continuing subtrees that continue the developmental process and arithmetic-performing subtrees that determine the numerical value of components. Topology-modifying functions have one or more construction-continuing subtrees, but no arithmetic-performing subtree. Component-creating functions have one or more construction-continuing subtrees and typically have one arithmetic-performing subtree. This constrained syntactic structure is preserved using structure-preserving crossover with point typing.
The foregoing method for automatically creating circuit topology and sizing does not address the problem of automatically placing and routing of components and wires at particular physical locations on a printed circuit board or silicon wafer.
References Cited
U.S. Patents
U.S. Pat. No. 4,697,242, xe2x80x9cAdaptive Computing System Capable of Learning and Discoveryxe2x80x9d, issued Sep. 29, 1987, Holland et al.
U.S. Pat. No. 4,881,178, xe2x80x9cMethod of Controlling a Classifier System,xe2x80x9d issued Nov. 14, 1989, Holland et al.
U.S. Pat. No. 4,935,877, xe2x80x9cNon-Linear Genetic Algorithms for Solving Problems,xe2x80x9d issued Jun. 19, 1990, Koza.
U.S. Pat. No. 5,136,686, xe2x80x9cNon-Linear Genetic Algorithms for Solving Problems by Finding a Fit Composition of Functions,xe2x80x9d issued Aug. 4, 1992, Koza.
U.S. Pat. No. 5,148,513, xe2x80x9cA Non-Linear Genetic Process for Use with Plural Co-Evolving Populations,xe2x80x9d issued Sep. 15, 1992, Koza, John R., and Rice, James P.
U.S. Pat. No. 5,343,554, xe2x80x9cA Non-Linear Genetic Process for Data Encoding and for Solving Problems Using Automatically Defined Functions,xe2x80x9d issued Aug. 30, 1994, Koza, John R., and Rice, James P.
U.S. Pat. No. 5,742,738, xe2x80x9cSimultaneous Evolution of the Architecture of a Multi-part Program to Solve a Problem Using Architecture Altering Operations,xe2x80x9d issued Apr. 21, 1998, Koza, John R., Andre, David, and Tackett, Walter Alden.
U.S. Pat. No. 5,867,397, xe2x80x9cMethod and Apparatus for Automated Design of Complex Structures Using Genetic Programmingxe2x80x9d, issued Feb. 2, 1999, Koza, John R., Bennett III, Forrest H., and Andre, David.
Other Publications
Grimbleby, J. B., Automatic analogue network synthesis using genetic algorithms. Proceedings of the First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications. London: Institution of Electrical Engineers, 1995.
Holland, John H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Ann Arbor, Mich.: University of Michigan Press. Second edition. Cambridge, Ma.: The MIT Press, 1975.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing. Science 220, pages 671-680.
Koza, John R., Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, Ma.: The MIT Press, 1992.
Koza, John R., Genetic Programming II: Automatic Discovery of Reusable Programs. Cambridge, Ma.: The MIT Press, 1994.
Kruiskamp, Wim and Leenaerts, Domine, DARWIN: CMOS opamp synthesis by means of a genetic algorithm. Proceedings of the 32nd Design Automation Conference. New York, N.Y.: Association for Computing Machinery, 1995.
Schnecke, V. and Vomberger, O. 1995. Genetic design of VLSI layouts. Proceedings of the First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications (GALESIA). London: Institution of Electrical Engineers, pages 430-435.
Sterling, Thomas L., Salmon, John, and Becker, Donald J., and Savarese, How to Build a Beowulf: A Guide to Implementation and Application of PC Clusters. Cambridge, Ma.: The MIT Press, 1999.
Thompson, Adrian, Silicon evolution. In Koza, John R., Goldberg, David E., Fogel, David B., and Riolo, Rick L. (editors), Genetic Programming 1996: Proceedings of the First Annual Conference. Cambridge, Ma.: MIT Press, 1996.
A method and apparatus for the automatic creation of the topology, component sizing, placement, and routing of complex structures, such as, but not limited to, analog and digital circuits. In one embodiment, the present invention operates with a system having a population of entities, of various sizes and shapes, in which the entities include constructing actions. An iterative process may be run to create a design of a structure that satisfies prespecified high-level design goals. In one embodiment, iteratively executing constructing actions in entities in the population results in the development of a structure that has components connected in a topological arrangement, where each component possesses a component value and occupies a particular physical location.